package java学习.算法.动态规划.暴力递归与动态规划;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/17 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 玩家抽取纸牌问题 {
    /**
     * 给定一个整形数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌。
     * 规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，
     * 玩家A和玩家B都绝顶聪明。请赶回最后获胜者的分数
     */
    public static void main(String[] args) {
        int[] arr = {4, 7, 9, 5, 19, 29, 80, 4,453};
        int[] arr1 = {4, 7, 9, 5, 10};
/**
 *
 */
/*
    A 10  7   5
    B 4   9
 */
        System.out.println(winOrfailure(arr1));
    }
    public  static  int winOrfailure (int[] arr ){

        if (arr==null||arr.length==0){
            return 0;
        }
        return Math.max(
                A(arr,0,arr.length-1),
                B(arr,0,arr.length-1)
                );


    }

    private static int A(int[] arr, int l, int r) {
        if (l==r){  // 若只有一张牌：A拿
            return arr[l];
        }
//        A拿左侧牌, 之后开始后手
        int res = Math.max(
                arr[l]+B(arr,l+1,r),
                arr[r]+B(arr,l,r-1));
        return res;

//        A拿右侧牌
    }
    private static int B(int[] arr, int l, int r) {
        if (l==r){
            return 0;
        }
        // A拿完后，B得到A剩下的最小值。
        return  Math.min(
                A(arr,l+1,r),
                A(arr, l, r-1));

    }

}
